package 动态规划.可dp可二分;

public class leetcode813分成k组最大平均和 {

	public static double solution(int nums[],int k) {
		int len = nums.length;
		int preSum []  = new int [len + 1];
		for(int i = 0;i < len ;i++) {
			preSum[i + 1] = preSum[i] + nums[i];
		}

		return recursion(0,k,len,nums,preSum);
	}

	public static double recursion(int index,int k,int len,int nums[],int preSum[]) {
		if(index == len)
			return k == 0 ? 0 : Integer.MIN_VALUE;
		if( k == 0)
			return Integer.MIN_VALUE;


		double ans = Integer.MIN_VALUE;
		for(int scale = 1; index + scale <= len;scale++) {
			ans = Math.max(ans, recursion(index + scale,k - 1,len,nums,preSum) + (preSum[index + scale] - preSum[index]) / (double)(scale));
		}
//		System.out.println(ans);
		return ans;
	}


	/*
	这个是有重复过程的并不是没有重复过程
	而且重复的过程举几个例子就明白了
	 */

	public static double dp(int nums[], int k){
		int len = nums.length;
		double dp[][]  =  new double[len + 1][k + 1];
		int [] preSum = new int [len + 1];
		for(int i = 0;i < len ; i++){
			preSum[i + 1] = preSum[i] + nums[i];
		}
		// 进行初始化
//		Arrays.fill(dp,(double)Integer.MIN_VALUE);
		for(int i = 0;i <= k;i++){
			dp[len][i] = Integer.MIN_VALUE;
		}
		for(int i = 0;i <= len;i++){
			dp[i][0] = Integer.MIN_VALUE;
		}
		// 初始化 basecase
		dp[len][0] = 0;
		for(int index = len  - 1; index >= 0;index--){
			for(int j = 1;j <= k;j++){
				double ans = Integer.MIN_VALUE;
				for(int scale  = 1;scale + index <= len;scale ++) {
					ans = Math.max(ans, dp[index + scale][j - 1] + (preSum[index + scale] - preSum[index]) / (double)(scale));
				}
				dp[index][j] = ans;
			}
		}
		return dp[0][k];
	}

	/**
	  无法 进行线性 的优化 ！
	 */
	public static double dpTest(int nums[], int k){
		int len = nums.length;
		double dp[][]  =  new double[len + 1][k + 1];
		int [] preSum = new int [len + 1];
		for(int i = 0;i < len ; i++){
			preSum[i + 1] = preSum[i] + nums[i];
		}
		// 进行初始化
//		Arrays.fill(dp,(double)Integer.MIN_VALUE);
		for(int i = 0;i <= k;i++){
			dp[len][i] = Integer.MIN_VALUE;
		}
		for(int i = 0;i <= len;i++){
			dp[i][0] = Integer.MIN_VALUE;
		}
		// 初始化 basecase
		dp[len][0] = 0;
		for(int index = len  - 1; index >= 0;index--){
			for(int j = 1;j <= k;j++){
				double ans = Integer.MIN_VALUE;
				for(int scale  = 1;scale + index <= len;scale ++) {
					ans = Math.max(ans, dp[index + scale][j - 1] + (preSum[index + scale] - preSum[index]) / (double)(scale));
				}
				dp[index][j] = ans;
			}
		}
		return dp[0][k];
	}


	public static void main(String []args) {


//		int nums []  = {9,1,2,3,9};
		int nums [] = {7,6,5,4,3,2,1};
		int nums1 [] = {1,2,3,4,5};
		int k = 4;
//		System.out.println(Double.MIN_VALUE);
//		System.out.println(-Double.MIN_VALUE + 1.0);
		System.out.println((double)Integer.MIN_VALUE);
		System.out.println((double)Integer.MIN_VALUE + 1);
		System.out.println(solution(nums,k));
		System.out.println(solution(nums1,k));
		System.out.println(dp(nums,k));
		System.out.println(dpTest(nums,k));
//		System.out.println(greedy(nums,k));
	}

}
